// 给定一个非负整数n，统计小于n的质数数量
function isPrime(x) {
    let len = Math.floor(Math.pow(x, 0.5)) + 1
    for (let i = 2; i < len; i++) {
        if (x % i === 0) {
            return false
        }        
    }
    return true
}

function countPrimes(n) {
    let count = 0
    for (let i = 2; i < n; i++) {
        if (isPrime(i)) {
            count++
        }
    }
    return count
}

console.log(countPrimes(6));
console.log(isPrime(3));


// 常规筛法
function countPrimes(n) {
    const dp = new Array(n).fill(true)
    let count = 0
    for (let i = 2; i < n; i++) {
        if (dp[i]) {
            count++
            for (let j = i * i; j < n; j += i) {
                dp[j] = false               
            }
        }
    }
    return count
}